#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    vector<int> smallestMissingValueSubtree(vector<int>& parents, vector<int>& nums) {
        int n = parents.size();
        vector<int> ans(n, 1);
        int num1 = -1;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] == 1)num1 = i;
        }

        if (num1 == -1)return ans;

        vector<vector<int>> g(n);
        for (int i = 1; i < n; i++) {
            g[parents[i]].push_back(i);
        }
        unordered_set<int> v;
        stack<int> nodes;
        int node = num1;
        int pre = -1;
        int mex = 2;
        while (node >= 0) {
            v.insert(nums[node]);
            for (auto son : g[node]) {
                if (son != pre) {
                    nodes.push(son);
                }
            }
            while (!nodes.empty()) {
                auto it = nodes.top();
                nodes.pop();
                v.insert(nums[it]);

                for (auto son : g[it]) {
                    nodes.push(son);
                }
            }
            while (v.count(mex)) {
                mex++;
            }
            ans[node] = mex;
            pre = node;
            node = parents[node];
        }
        return ans;
    }
};